package Test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;

public class Demo4 {
    public static int max2(int bag,int[] w,int[] v){
        int N=w.length;
        int[][] dp=new int[N+1][bag+1];
        for(int index=w.length-1;index>=0;index--){
            for(int rest=0;rest<=bag;rest++){
                int p1=dp[index+1][rest];
                int p2=rest-w[index]<0?-1:dp[index+1][rest-w[index]]+v[index];
                dp[index][rest]=Math.max(p1,p2);
            }
        }
        return dp[0][bag];
    }
      public static int max(int[] w,int[] v,int index,int Bag){
           if(Bag<0){
               return -1;
           }
           if(index==w.length){
               return 0;
           }
           int p1=max(w,v,index+1,Bag);
           int p2=Bag-w[index]<0?-1:v[index]+max(w,v,index+1,Bag-w[index]);
           return Math.max(p1,p2);
      }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int BigWeight=sc.nextInt();
        int[] w=new int[N+1];
        int[] v=new int[N+1];
        for (int i = 0; i < N; i++) {
            w[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }
        int[][] dp=new int[N+1][BigWeight+1];
        System.out.println(max2(BigWeight,w,v));
    }
}
